package j2025.j02;

/**
 * @Author 猫大仙
 */
public class j0216 {
    /**
     * 76. 最小覆盖子串
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {
        char[] str = s.toCharArray();
        char[] tr = t.toCharArray();
        int[] hs = new int[128];
        int[] ht = new int[128];
        int kind = 0;
        int minlen = Integer.MAX_VALUE;
        int begin = -1;
        for (int i = 0; i < tr.length; i++) {
            if(ht[tr[i]]==0){
                kind++;
            }
            ht[tr[i]]++;
        }
        for (int left = 0,right=0,count=0; right < s.length(); right++) {
            //进入子串中
            char in = str[right];
            hs[in]++;
            if(hs[in]==ht[in]){
                count++;
            }
            //统计结果,出子串
            while(count==kind){
                int len = right-left+1;
                if(len<minlen){
                    minlen = len;
                    begin = left;
                }
                char out = str[left++];
                if(hs[out]==ht[out]){
                    count--;
                }
                hs[out]--;
            }
        }
        if(begin==-1){
            return "";
        }else {
            return s.substring(begin,begin+minlen);
        }
    }
}
